package leetcode010;



public class Study010 {

    public boolean isMatch(String s, String p) {
        s = " " + s;
        p = " " + p;
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始化
        dp[0][0] = true;


        for ( int i = 1; i <= m; i++ ) {
            for ( int j = 1; j <= n; j++ ) {
                //s的当前字符
                char sc = s.charAt(i - 1);
                //p的当前字符
                char pc = p.charAt(j - 1);
                //如果后一位是*，则跳过当前位匹配
                if ( j + 1 <= n && p.charAt(j) == '*' ) {
                    continue;
                }
                if(pc != '*'){//pc不为*
                    dp[i][j] = dp[i-1][j-1] && isMatch(sc, pc);
                } else {//pc为*
                    int x = 2;
                    //往前找*对应的字符是哪个
                    while (j - x >= 0 && p.charAt(j - x) == '*') {
                        x++;
                    }
                    if (p.charAt(j - x) == '*') {
                        return false;
                    }
                    if (isMatch(sc, p.charAt(j - x))) {
                        dp[i][j] = dp[i][j - x] || dp[i - 1][j - x] || dp[i - 1][j] ;
                    } else {
                        dp[i][j] = dp[i][j-x];
                    }
                }
            }
        }
        return dp[m][n];
    }

    private boolean isMatch(char s, char p) {
        if (p == '.') {
            return true;
        } else {
            return s == p;
        }
    }


    public static void main(String[] args){
        Study010 s = new Study010();
        System.out.println(s.isMatch("a", "a.*"));

        System.out.println(s.isMatch("aa", "a*a"));
        System.out.println(s.isMatch("aa", "a.*a"));
        System.out.println(s.isMatch("aab", "c*a*b"));
        System.out.println(s.isMatch("mississippi", "mis*is*ip*."));
        System.out.println(s.isMatch("mississipppppppia", "mis*is*ip*p.a"));
        System.out.println(s.isMatch("abc", "a***abc"));
        System.out.println(s.isMatch("a", ".*..a*"));
        System.out.println(s.isMatch("aab", "b.*"));
        System.out.println(s.isMatch("aa", "aaaa*"));

        System.out.println(s.isMatch("aa", "a"));
    }
}
